package 开始的算法算法入门8月.递归回朔;

import java.util.ArrayList;
import java.util.List;

// https://leetcode-cn.com/problems/letter-case-permutation/
public class 字母大小写全排列7840822 {
    class Solution {
        public List<String> letterCasePermutation(String S) {
            List<StringBuilder> ans = new ArrayList();

            ans.add(new StringBuilder());

            for (char c: S.toCharArray()) {
                int n = ans.size();
                if (Character.isLetter(c)) {
                    for (int i = 0; i < n; ++i) {
                        ans.add(new StringBuilder(ans.get(i)));
                        ans.get(i).append(Character.toLowerCase(c));
                        ans.get(n+i).append(Character.toUpperCase(c));
                    }
                } else {
                    for (int i = 0; i < n; ++i)
                        ans.get(i).append(c);
                }
            }

            List<String> finalans = new ArrayList();
            for (StringBuilder sb: ans)
                finalans.add(sb.toString());
            return finalans;
        }
    }


}
